import java.util.*;

class Floyd_Warshall {
	static final int MAX = 20; // 最大点数
	static double[][] W; // 权重
	static int ver; // 点数
	static int edge; // 边数
	static double[][] D; // i到j最小权重和
	static int[][] pre; // 记录前驱节点

	// O(n^3)
	static void floyd_warshall() {
		initD();
		for (int k = 1; k <= ver; k++) {
			for (int i = 1; i <= ver; i++) {
				for (int j = 1; j <= ver; j++) {
					// 防止溢出
					if (D[i][k] == Integer.MAX_VALUE || D[k][j] == Integer.MAX_VALUE)
						continue;

					if (D[i][k] + D[k][j] < D[i][j]) {
						/*
						 * 对于任意节点对i,j,考虑从i到j的所有中间节点取自{1,2...k}的路径，并设p为其中
						 * 权重最小的路径。
						 * 如果节点k不是路径p上的中间节点，则路径p上的所有中间节点都属于集合{1,2,..k-1}
						 * 因此从i到j的中间节点取自集合{1,2..k-1}的一条最短路径也是从i到j取自{1,2,..k}的
						 * 一条最短路径
						 * 
						 * 如果k是路径p的中间节点,则将路径p分解成i~k(p1)~j(p2),p1是从节点i到节点k的中间节点
						 * 全部取自集合{1,2...,k-1}的一条最短路径，类似的，p2是从k到j的中间节点全部取自集合
						 * {1,2..k-1}的一条最短路径
						 */
						D[i][j] = D[i][k] + D[k][j]; // 递推公式
						// 此时i到j分成i到k,k到j两段;由if条件知，这里k!=i,k!=j
						pre[i][j] = pre[k][j];
					}
				}
			}
		}
	}

	static void init() {
		W = new double[ver + 5][ver + 5];
		D = new double[ver + 5][ver + 5];
		pre = new int[ver + 5][ver + 5];
		for (int i = 1; i <= ver; i++)
			for (int j = 1; j <= ver; j++) {
				if (i == j)
					W[i][j] = 0;
				else
					W[i][j] = Integer.MAX_VALUE;
			}
	}

	static void input() {
		Scanner cin = new Scanner(System.in);
		System.out.println("请输入 点数 边数");
		ver = cin.nextInt();
		edge = cin.nextInt();
		int s, e;
		double w;
		init();
		System.out.println("起点 终点 权值");
		for (int i = 0; i < edge; i++) {
			s = cin.nextInt();
			e = cin.nextInt();
			w = cin.nextDouble();
			W[s][e] = w;
		}
	}

	static void initD() {
		for (int i = 1; i <= ver; i++)
			for (int j = 1; j <= ver; j++) {
				/*
				 * k=0时，从i到j的一条不包括编号大于0的节点的 路径将没有中间节点。这样的路径最多只有一条边,
				 * 所以当ij不可达时，D[i][j] = W[i][j]=Infinity, i到j可达时，D[i][j] =
				 * W[i][j]
				 */
				D[i][j] = W[i][j];
				/* 此时如果i==j,j没有前驱节点，设为-1（NIL）；否则j的前驱节点就是i */
				pre[i][j] = (i == j) ? -1 : i;
			}
	}

	static void print() {
		System.out.println("\nD[][]:");
		for (int i = 1; i <= ver; i++) {
			for (int j = 1; j <= ver; j++) {
				System.out.print(D[i][j] + "\t");
			}
			System.out.println("\n");
		}
	}

	static void print_shortest_path(int i, int j) {
		if (i == j)
			System.out.print(i);
		else if (pre[i][j] == -1)
			System.out.println("no path from i to j exists");
		else
			print_shortest_path(i, pre[i][j]);
		if (i != j)
			System.out.print("-" + j);
	}

	static void print_all_pairs_shortest_path() {
		System.out.println("节点对最短路径:");
		for (int i = 1; i <= ver; i++) {
			for (int j = 1; j <= ver; j++) {
				System.out.println(i + "-->" + j + ":");
				print_shortest_path(i, j);
				System.out.println();
			}
		}
	}

	public static void main(String[] args) {
		input();
		floyd_warshall();
		print();
		print_all_pairs_shortest_path();
	}
}